package org.apache.lucene.util;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/* Derived from org.apache.lucene.util.PriorityQueue of March 2005 */

import java.io.IOException;

import org.apache.lucene.search.DocIdSetIterator;
import org.apache.lucene.search.Scorer;

/** A ScorerDocQueue maintains a partial ordering of its Scorers such that the
  least Scorer can always be found in constant time.  Put()'s and pop()'s
  require log(size) time. The ordering is by Scorer.doc().
 *
 * @lucene.internal
 */
public class ScorerDocQueue { // later: SpansQueue for spans with doc and term positions
    private final HeapedScorerDoc[] heap;
    private final int maxSize;
    private int size;

    private class HeapedScorerDoc {
        Scorer scorer;
        int doc;

        HeapedScorerDoc(Scorer s) {
            this(s, s.docID());
        }

        HeapedScorerDoc(Scorer scorer, int doc) {
            this.scorer = scorer;
            this.doc = doc;
        }

        void adjust() {
            doc = scorer.docID();
        }
    }

    private HeapedScorerDoc topHSD; // same as heap[1], only for speed

    /** Create a ScorerDocQueue with a maximum size. */
    public ScorerDocQueue(int maxSize) {
        // assert maxSize >= 0;
        size = 0;
        int heapSize = maxSize + 1;
        heap = new HeapedScorerDoc[heapSize];
        this.maxSize = maxSize;
        topHSD = heap[1]; // initially null
    }

    /**
     * Adds a Scorer to a ScorerDocQueue in log(size) time.
     * If one tries to add more Scorers than maxSize
     * a RuntimeException (ArrayIndexOutOfBound) is thrown.
     */
    public final void put(Scorer scorer) {
        size++;
        heap[size] = new HeapedScorerDoc(scorer);
        upHeap();
    }

    /**
     * Adds a Scorer to the ScorerDocQueue in log(size) time if either
     * the ScorerDocQueue is not full, or not lessThan(scorer, top()).
     * @param scorer
     * @return true if scorer is added, false otherwise.
     */
    public boolean insert(Scorer scorer) {
        if (size < maxSize) {
            put(scorer);
            return true;
        } else {
            int docNr = scorer.docID();
            if ((size > 0) && (!(docNr < topHSD.doc))) { // heap[1] is top()
                heap[1] = new HeapedScorerDoc(scorer, docNr);
                downHeap();
                return true;
            } else {
                return false;
            }
        }
    }

    /** Returns the least Scorer of the ScorerDocQueue in constant time.
     * Should not be used when the queue is empty.
     */
    public final Scorer top() {
        // assert size > 0;
        return topHSD.scorer;
    }

    /** Returns document number of the least Scorer of the ScorerDocQueue
     * in constant time.
     * Should not be used when the queue is empty.
     */
    public final int topDoc() {
        // assert size > 0;
        return topHSD.doc;
    }

    public final float topScore() throws IOException {
        // assert size > 0;
        return topHSD.scorer.score();
    }

    public final boolean topNextAndAdjustElsePop() throws IOException {
        return checkAdjustElsePop(topHSD.scorer.nextDoc() != DocIdSetIterator.NO_MORE_DOCS);
    }

    public final boolean topSkipToAndAdjustElsePop(int target) throws IOException {
        return checkAdjustElsePop(topHSD.scorer.advance(target) != DocIdSetIterator.NO_MORE_DOCS);
    }

    private boolean checkAdjustElsePop(boolean cond) {
        if (cond) { // see also adjustTop
            topHSD.doc = topHSD.scorer.docID();
        } else { // see also popNoResult
            heap[1] = heap[size]; // move last to first
            heap[size] = null;
            size--;
        }
        downHeap();
        return cond;
    }

    /** Removes and returns the least scorer of the ScorerDocQueue in log(size)
     * time.
     * Should not be used when the queue is empty.
     */
    public final Scorer pop() {
        // assert size > 0;
        Scorer result = topHSD.scorer;
        popNoResult();
        return result;
    }

    /** Removes the least scorer of the ScorerDocQueue in log(size) time.
     * Should not be used when the queue is empty.
     */
    private final void popNoResult() {
        heap[1] = heap[size]; // move last to first
        heap[size] = null;
        size--;
        downHeap(); // adjust heap
    }

    /** Should be called when the scorer at top changes doc() value.
     * Still log(n) worst case, but it's at least twice as fast to <pre>
     *  { pq.top().change(); pq.adjustTop(); }
     * </pre> instead of <pre>
     *  { o = pq.pop(); o.change(); pq.push(o); }
     * </pre>
     */
    public final void adjustTop() {
        // assert size > 0;
        topHSD.adjust();
        downHeap();
    }

    /** Returns the number of scorers currently stored in the ScorerDocQueue. */
    public final int size() {
        return size;
    }

    /** Removes all entries from the ScorerDocQueue. */
    public final void clear() {
        for (int i = 0; i <= size; i++) {
            heap[i] = null;
        }
        size = 0;
    }

    private final void upHeap() {
        int i = size;
        HeapedScorerDoc node = heap[i]; // save bottom node
        int j = i >>> 1;
        while ((j > 0) && (node.doc < heap[j].doc)) {
            heap[i] = heap[j]; // shift parents down
            i = j;
            j = j >>> 1;
        }
        heap[i] = node; // install saved node
        topHSD = heap[1];
    }

    private final void downHeap() {
        int i = 1;
        HeapedScorerDoc node = heap[i]; // save top node
        int j = i << 1; // find smaller child
        int k = j + 1;
        if ((k <= size) && (heap[k].doc < heap[j].doc)) {
            j = k;
        }
        while ((j <= size) && (heap[j].doc < node.doc)) {
            heap[i] = heap[j]; // shift up child
            i = j;
            j = i << 1;
            k = j + 1;
            if (k <= size && (heap[k].doc < heap[j].doc)) {
                j = k;
            }
        }
        heap[i] = node; // install saved node
        topHSD = heap[1];
    }
}
